|
In computer algebra, the Faugère F4 algorithm, by Jean-Charles Faugère, computes the Gröbner basis of an ideal of a multivariate polynomial ring. The algorithm uses the same mathematical principles as the Buchberger algorithm, but computes many normal forms in one go by forming a generally sparse matrix and using fast linear algebra to do the reductions in parallel. The Faugère F5 algorithm first calculates the Gröbner basis of a pair of generator polynomials of the ideal. Then it uses this basis to reduce the size of the initial matrices of generators for the next larger basis:
This strategy allows the algorithm to apply two new criteria based on what Faugère calls ''signatures'' of polynomials. Thanks to these criteria, the algorithm can compute Gröbner bases for a large class of interesting polynomial systems, called ''regular sequences'', without ever simplifying a single polynomial to zero—the most time-consuming operation in algorithms that compute Gröbner bases. It is also very effective for a large number of non-regular sequences. == Implementations == The Faugère F4 algorithm is implemented * as a (package FGb ) for the Maple computer algebra system. This package is included in Maple distribution as the option method=fgb of function Groebner(); * in the Magma computer algebra system. * as a (C library ). Study versions of the Faugère F5 algorithm is implemented in * the SINGULAR computer algebra system; * the Sage computer algebra system. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Faugère's F4 and F5 algorithms」の詳細全文を読む スポンサード リンク
|